Escape a large maze

Time: O(N^2); Space: O(N); hard

In a 1 million by 1 million grid, the coordinates of each grid square are (x, y) with 0 <= x, y < 10^6.

We start at the source square and want to reach the target square. Each move, we can walk to a 4-directionally adjacent square in the grid that isn’t in the given list of blocked squares.

Return true if and only if it is possible to reach the target square through a sequence of moves.

Example 1:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]

Output: False

Explanation:

  • The target square is inaccessible starting from the source square, because we can’t walk outside the grid.

Example 2:

Input: blocked = [], source = [0,0], target = [999999,999999]

Output: True

Explanation:

  • Because there are no blocked cells, it’s possible to reach the target square.

Note:

  • 0 <= len(blocked) <= 200

  • len(blocked[i]) == 2

  • 0 <= blocked[i][j] < 10^6

  • len(source) == len(target) == 2

  • 0 <= source[i][j], target[i][j] < 10^6

  • source != target

[1]:

import collections

class Solution1(object):
    """
    Time:  O(n^2), n is the number of blocked.
    Space: O(n).
    """
    def isEscapePossible(self, blocked, source, target):
        """
        :type blocked: List[List[int]]
        :type source: List[int]
        :type target: List[int]
        :rtype: bool
        """
        R, C = 10**6, 10**6
        directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]

        def bfs(blocks, source, target):
            max_area_surrounded_by_blocks = len(blocks)*(len(blocks)-1)//2
            lookup = set([source])
            if len(lookup) > max_area_surrounded_by_blocks:
                return True

            q = collections.deque([source])
            while q:
                source = q.popleft()
                if source == target:
                    return True

                for direction in directions:
                    nr, nc = source[0] + direction[0], source[1] + direction[1]
                    if not ((0 <= nr < R) and
                            (0 <= nc < C) and
                            (nr, nc) not in lookup and
                            (nr, nc) not in blocks):
                        continue
                    lookup.add((nr, nc))
                    if len(lookup) > max_area_surrounded_by_blocks:
                        return True
                    q.append((nr, nc))
            return False

        return bfs(set(map(tuple, blocked)), tuple(source), tuple(target)) and \
               bfs(set(map(tuple, blocked)), tuple(target), tuple(source))

[2]:

s = Solution1()
blocked = [[0,1],[1,0]]
source = [0,0]
target = [0,2]
assert s.isEscapePossible(blocked, source, target) == False

blocked = []
source = [0,0]
target = [999999,999999]
assert s.isEscapePossible(blocked, source, target) == True